Chicken » Unit srfi-14

Unit srfi-14

Character set library. An abbreviated version of the SRFI is provided in this document. Full documentation is available in the original SRFI-14 document.

On systems that support dynamic loading, the srfi-14 unit can be made available in the interpreter (csi) by entering

(require-extension srfi-14)

This library provides only the Latin-1 character set. To get Unicode semantics, see the utf8 egg. However, information on Unicode character sets is still provided in this document.

Specification

In the following procedure specifications:

A CS parameter is a character set.
An S parameter is a string.
A CHAR parameter is a character.
A CHAR-LIST parameter is a list of characters.
A PRED parameter is a unary character predicate procedure, returning a true/false value when applied to a character.
An OBJ parameter may be any value at all.

Passing values to procedures with these parameters that do not satisfy these types is an error.

Unless otherwise noted in the specification of a procedure, procedures always return character sets that are distinct (from the point of view of the linear-update operations) from the parameter character sets. For example, char-set-adjoin is guaranteed to provide a fresh character set, even if it is not given any character parameters.

Parameters given in square brackets are optional. Unless otherwise noted in the text describing the procedure, any prefix of these optional parameters may be supplied, from zero arguments to the full list. When a procedure returns multiple values, this is shown by listing the return values in square brackets, as well. So, for example, the procedure with signature

halts? F [X INIT-STORE] -> [BOOLEAN INTEGER]

would take one (F), two (F, X) or three (F, X, INIT-STORE) input parameters, and return two values, a boolean and an integer.

A parameter followed by "..." means zero-or-more elements. So the procedure with the signature

sum-squares X ...  -> NUMBER

takes zero or more arguments (X ...), while the procedure with signature

spell-check DOC DICT_1 DICT_2 ... -> STRING-LIST

takes two required parameters (DOC and DICT_1) and zero or more optional parameters (DICT_2 ...).

General procedures

(char-set? obj) -> boolean procedure: Is the object OBJ a character set?

(char-set= cs_1 ...) -> boolean procedure

Are the character sets equal?

Boundary cases:

(char-set=) => TRUE
(char-set= cs) => TRUE

Rationale: transitive binary relations are generally extended to n-ary relations in Scheme, which enables clearer, more concise code to be written. While the zero-argument and one-argument cases will almost certainly not arise in first-order uses of such relations, they may well arise in higher-order cases or macro-generated code. E.g., consider

(apply char-set= cset-list)

This is well-defined if the list is empty or a singleton list. Hence we extend these relations to any number of arguments. Implementors have reported actual uses of n-ary relations in higher-order cases allowing for fewer than two arguments. The way of Scheme is to handle the general case; we provide the fully general extension.

A counter-argument to this extension is that R5RS's transitive binary arithmetic relations (=, <, etc.) require at least two arguments, hence this decision is a break with the prior convention -- although it is at least one that is backwards-compatible.

(char-set<= cs_1 ...) -> boolean procedure

Returns true if every character set CS_I is a subset of character set CS_I+1.

Boundary cases:

(char-set<=) => TRUE
(char-set<= cs) => TRUE

Rationale: See char-set= for discussion of zero- and one-argument applications. Consider testing a list of char-sets for monotonicity with

(apply char-set<= cset-list)

(char-set-hash cs [bound]) -> integer procedure

Compute a hash value for the character set CS. BOUND is a non-negative exact integer specifying the range of the hash function. A positive value restricts the return value to the range [0,BOUND).

If BOUND is either zero or not given, the implementation may use an implementation-specific default value, chosen to be as large as is efficiently practical. For instance, the default range might be chosen for a given implementation to map all strings into the range of integers that can be represented with a single machine word.

Invariant:

(char-set= cs_1 cs_2) => (= (char-set-hash cs_1 b) (char-set-hash cs_2 b))

A legal but nonetheless discouraged implementation:

(define (char-set-hash cs . maybe-bound) 1)

Rationale: allowing the user to specify an explicit bound simplifies user code by removing the mod operation that typically accompanies every hash computation, and also may allow the implementation of the hash function to exploit a reduced range to efficiently compute the hash value. E.g., for small bounds, the hash function may be computed in a fashion such that intermediate values never overflow into bignum integers, allowing the implementor to provide a fixnum-specific "fast path" for computing the common cases very rapidly.

Iterating over character sets

(char-set-cursor cset) -> cursor procedure

(char-set-ref cset cursor) -> char procedure

(char-set-cursor-next cset cursor) -> cursor procedure

(end-of-char-set? cursor) -> boolean procedure

Cursors are a low-level facility for iterating over the characters in a set. A cursor is a value that indexes a character in a char set. char-set-cursor produces a new cursor for a given char set. The set element indexed by the cursor is fetched with char-set-ref. A cursor index is incremented with char-set-cursor-next; in this way, code can step through every character in a char set. Stepping a cursor "past the end" of a char set produces a cursor that answers true to end-of-char-set?. It is an error to pass such a cursor to char-set-ref or to char-set-cursor-next.

A cursor value may not be used in conjunction with a different character set; if it is passed to char-set-ref or char-set-cursor-next with a character set other than the one used to create it, the results and effects are undefined.

Cursor values are not necessarily distinct from other types. They may be integers, linked lists, records, procedures or other values. This license is granted to allow cursors to be very "lightweight" values suitable for tight iteration, even in fairly simple implementations.

Note that these primitives are necessary to export an iteration facility for char sets to loop macros.

Example:

(define cs (char-set #\G #\a #\T #\e #\c #\h))
 
;; Collect elts of CS into a list.
(let lp ((cur (char-set-cursor cs)) (ans '()))
  (if (end-of-char-set? cur) ans
      (lp (char-set-cursor-next cs cur)
          (cons (char-set-ref cs cur) ans))))
  => (#\G #\T #\a #\c #\e #\h)
 
;; Equivalently, using a list unfold (from SRFI 1):
(unfold-right end-of-char-set? 
              (curry char-set-ref cs)
	      (curry char-set-cursor-next cs)
	      (char-set-cursor cs))
  => (#\G #\T #\a #\c #\e #\h)

Rationale: Note that the cursor API's four functions "fit" the functional protocol used by the unfolders provided by the list, string and char-set SRFIs (see the example above). By way of contrast, here is a simpler, two-function API that was rejected for failing this criterion. Besides char-set-cursor, it provided a single function that mapped a cursor and a character set to two values, the indexed character and the next cursor. If the cursor had exhausted the character set, then this function returned false instead of the character value, and another end-of-char-set cursor. In this way, the other three functions of the current API were combined together.

(char-set-fold kons knil cs) -> object procedure

This is the fundamental iterator for character sets. Applies the function KONS across the character set CS using initial state value KNIL. That is, if CS is the empty set, the procedure returns KNIL. Otherwise, some element C of CS is chosen; let CS' be the remaining, unchosen characters. The procedure returns

(char-set-fold KONS (KONS C KNIL) CS')

Examples:

;; CHAR-SET-MEMBERS
(lambda (cs) (char-set-fold cons '() cs))
 
;; CHAR-SET-SIZE
(lambda (cs) (char-set-fold (lambda (c i) (+ i 1)) 0 cs))
 
;; How many vowels in the char set?
(lambda (cs) 
  (char-set-fold (lambda (c i) (if (vowel? c) (+ i 1) i))
                 0 cs))

(char-set-unfold f p g seed [base-cs]) -> char-set procedure

(char-set-unfold! f p g seed base-cs) -> char-set procedure

This is a fundamental constructor for char-sets.

G is used to generate a series of "seed" values from the initial seed: SEED, (G SEED), (G^2 SEED), (G^3 SEED), ...
P tells us when to stop -- when it returns true when applied to one of these seed values.
F maps each seed value to a character. These characters are added to the base character set BASE-CS to form the result; BASE-CS defaults to the empty set. char-set-unfold! adds the characters to BASE-CS in a linear-update -- it is allowed, but not required, to side-effect and use BASE-CS's storage to construct the result.

More precisely, the following definitions hold, ignoring the optional-argument issues:

(define (char-set-unfold p f g seed base-cs) 
  (char-set-unfold! p f g seed (char-set-copy base-cs)))
 
(define (char-set-unfold! p f g seed base-cs)
  (let lp ((seed seed) (cs base-cs))
        (if (p seed) cs                                 ; P says we are done.
            (lp (g seed)                                ; Loop on (G SEED).
                (char-set-adjoin! cs (f seed))))))      ; Add (F SEED) to set.

(Note that the actual implementation may be more efficient.)

Examples:

(port->char-set p) = (char-set-unfold eof-object? values
                                      (lambda (x) (read-char p))
                                      (read-char p))
 
(list->char-set lis) = (char-set-unfold null? car cdr lis)

(char-set-for-each proc cs) -> unspecified procedure

Apply procedure PROC to each character in the character set CS. Note that the order in which PROC is applied to the characters in the set is not specified, and may even change from one procedure application to another.

Nothing at all is specified about the value returned by this procedure; it is not even required to be consistent from call to call. It is simply required to be a value (or values) that may be passed to a command continuation, e.g. as the value of an expression appearing as a non-terminal subform of a begin expression. Note that in R5RS, this restricts the procedure to returning a single value; non-R5RS systems may not even provide this restriction.

(char-set-map proc cs) -> char-set procedure

PROC is a char->char procedure. Apply it to all the characters in the char-set CS, and collect the results into a new character set.

Essentially lifts PROC from a char->char procedure to a char-set -> char-set procedure.

Example:

(char-set-map char-downcase cset)

Creating character sets

(char-set-copy cs) -> char-set procedure

Returns a copy of the character set CS. "Copy" means that if either the input parameter or the result value of this procedure is passed to one of the linear-update procedures described below, the other character set is guaranteed not to be altered.

A system that provides pure-functional implementations of the linear-operator suite could implement this procedure as the identity function -- so copies are not guaranteed to be distinct by eq?.

(char-set char_1 ...) -> char-set procedure: Return a character set containing the given characters.

(list->char-set char-list [base-cs]) -> char-set procedure

(list->char-set! char-list base-cs) -> char-set procedure